home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / ohlfind.zip / CODE.C < prev    next >
C/C++ Source or Header  |  1990-05-17  |  3KB  |  152 lines
  1. /* code -- code filenames for fast-find
  2.  
  3.    Compress a sorted list.
  4.    Works with 'find' to encode and decode a filename database.
  5.  
  6.    Usage:
  7.  
  8.    bigram < list > bigrams
  9.    process-bigrams > common_bigrams
  10.    code common_bigrams < list > squeezed_list
  11.  
  12.    Uses 'front compression' (see ";login:", March 1983, p. 8).
  13.    Output format is, per line, an offset differential count byte
  14.    followed by a partially bigram-encoded ASCII residue.
  15.    
  16.    The codes are:
  17.    
  18.    0-28        likeliest differential counts + offset to make nonnegative
  19.    30        escape code for out-of-range count to follow in next word
  20.    128-255     bigram codes (128 most common, as determined by 'updatedb')
  21.    32-127      single character (printable) ASCII residue
  22.  
  23.    Author: James A. Woods (jaw@riacs.edu)
  24.    Modified by David MacKenzie (djm@ai.mit.edu)
  25.    Public domain. */
  26.  
  27. #include <stdio.h>
  28. #include <sys/types.h>
  29. #include <sys/param.h>
  30.  
  31. #ifndef MAXPATHLEN
  32. #define MAXPATHLEN 1024
  33. #endif
  34.  
  35. /* Switch code. */
  36. #define    RESET    30
  37.  
  38. char path[MAXPATHLEN];
  39.  
  40. char oldpath[MAXPATHLEN] = " ";
  41.  
  42. char bigrams[257] = {0};
  43.  
  44. void
  45. main (argc, argv)
  46.      int argc;
  47.      char *argv[];
  48. {
  49.   int count, oldcount, diffcount;
  50.   int j, code;
  51.   char bigram[3];
  52.   FILE *fp;
  53.  
  54.   oldcount = 0;
  55.   bigram[2] = '\0';
  56.  
  57.   if (argc != 2)
  58.     {
  59.       fprintf (stderr, "Usage: %s common_bigrams < list > coded_list\n",
  60.            argv[0]);
  61.       exit (2);
  62.     }
  63.  
  64.   fp = fopen (argv[1], "r");
  65.   if (fp == NULL)
  66.     {
  67.       fprintf (stderr, "%s: ", argv[0]);
  68.       perror (argv[1]);
  69.       exit (1);
  70.     }
  71.  
  72.   fgets (bigrams, 257, fp);
  73.   fwrite (bigrams, 1, 256, stdout);
  74.  
  75.   while (fgets (path, sizeof path, stdin) != NULL)
  76.     {
  77.       path[strlen (path) - 1] = '\0'; /* Remove newline. */
  78.  
  79.       /* Squelch unprintable chars so as not to botch decoding. */
  80.       for (j = 0; path[j] != '\0'; j++)
  81.     {
  82.       path[j] &= 0177;
  83.       if (path[j] < 040 || path[j] == 0177)
  84.         path[j] = '?';
  85.     }
  86.       count = prefix_length (oldpath, path);
  87.       diffcount = count - oldcount;
  88.       if (diffcount < -14 || diffcount > 14)
  89.     {
  90.       putc (RESET, stdout);
  91.       putw (diffcount + 14, stdout);
  92.     }
  93.       else
  94.     putc (diffcount + 14, stdout);
  95.  
  96.       for (j = count; path[j] != '\0'; j += 2)
  97.     {
  98.       if (path[j + 1] == '\0')
  99.         {
  100.           putchar (path[j]);
  101.           break;
  102.         }
  103.       bigram[0] = path[j];
  104.       bigram[1] = path[j + 1];
  105.       /* Linear search for specific bigram in string table. */
  106.       code = strindex (bigrams, bigram);
  107.       if (code % 2 == 0)
  108.         putchar ((code / 2) | 0200);
  109.       else
  110.         fputs (bigram, stdout);
  111.     }
  112.       strcpy (oldpath, path);
  113.       oldcount = count;
  114.     }
  115.   exit (0);
  116. }
  117.  
  118. /* Return location of PATTERN in STRING or -1. */
  119.  
  120. int
  121. strindex (string, pattern)
  122.      char *string, *pattern;
  123. {
  124.   register char *s, *p, *q;
  125.  
  126.   for (s = string; *s != '\0'; s++)
  127.     if (*s == *pattern)
  128.       {
  129.     /* Fast first char check. */
  130.     for (p = pattern + 1, q = s + 1; *p != '\0'; p++, q++)
  131.       if (*q != *p)
  132.         break;
  133.     if (*p == '\0')
  134.       return q - strlen (pattern) - string;
  135.       }
  136.   return -1;
  137. }
  138.  
  139. /* Return length of longest common prefix of strings S1 and S2. */
  140.  
  141. int
  142. prefix_length (s1, s2)
  143.      char *s1, *s2;
  144. {
  145.   register char *start;
  146.  
  147.   for (start = s1; *s1 == *s2; s1++, s2++)
  148.     if (*s1 == '\0')
  149.       break;
  150.   return s1 - start;
  151. }
  152.